package ua.mykola.ds.map;

/**
 * Simplified dynamicly growing HashMap implementation.
 * @author Mykola
 *
 * @param <K> key
 * @param <V> value
 */
public class HashMap<K,V> implements Map<K,V>{
	private static final int DEFAULT_INIT_SIZE=16;
	private static final float DEFAULT_LOAD_FACTOR=0.75f;

	private Entity<K,V>[] array;
	private float loadFactor;
	private int threshold;
	private int size;
	
	private static class Entity<K,V>{
		private K key;
		private V value;
		private Entity(K key,V value){
			this.key=key;
			this.value=value;
		}
	}
	
	
	public HashMap(){
		array=new Entity[DEFAULT_INIT_SIZE];
		loadFactor=DEFAULT_LOAD_FACTOR;
		threshold=(int)(DEFAULT_INIT_SIZE*DEFAULT_LOAD_FACTOR);
	}
	
	public void put(K key,V value){
		int index=getIndex(key);
		put(index,new Entity<K,V>(key,value));
		size++;
		if(size>=threshold) resize();
	}
	
	private void resize(){
		Entity<K,V>[] oldTable=array;
		array=new Entity[oldTable.length*2];
		size=0;
		threshold=(int)(array.length*loadFactor);
		for(Entity<K,V> entity:oldTable){
			if(entity==null) continue;
			put(entity.key,entity.value);
		}
	}
	
	
	private int getIndex(K key){
		return Math.abs(key.hashCode()%array.length);
	}

	private int getNextIndex(int index){
		int nextIndex=index+1;
		if (nextIndex==array.length) nextIndex=0;
		return nextIndex;
	}
	
	private void put(int index,Entity<K,V> entity){
		if(array[index]==null) array[index]=entity;
		else  put(getNextIndex(index),entity);
	}

	public V get(K key){
		int index=getIndex(key);
		int entityIndex=findIndex(index,key);
		return entityIndex==-1?null:array[entityIndex].value;
	}

	private int findIndex(int index, K key){
		if(array[index]==null) return -1;
		else if(array[index].key.equals(key)) return index;
		return findIndex(getNextIndex(index),key);
	}
	
	
	public V remove(K key){
		int index=getIndex(key);
		int entityIndex=findIndex(index,key);
		if (entityIndex==-1) return null;
		else {
			V temp=array[entityIndex].value;
			array[entityIndex]=null;
			size--;
			return temp;
			}
	}

	public int getSize() {
		return size;
	}	
	
}
